import java.util.*;

public class 二叉树的锯齿形层序遍历 {
    //https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
    public static int HMAX = 2100;
    public static TreeNode[] queue = new TreeNode[HMAX];
    public static int l;
    public static int r;
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        //添加根节点
        if(root == null){
            return ret;
        }
        l = r = 0;
        queue[r++] = root;
        boolean rev = true;
        while(l < r){
            //每次弹出的元素, 创建这层的表
            int size = r - l;
            List<Integer> list = new ArrayList<>();
            //true从左往右, false从右往左
            if (rev){
                for (int i = l; i < r; i++) {
                    list.add(queue[i].val);
                }
            }else {
                for (int i = r - 1; i >= l; i--) {
                    list.add(queue[i].val);
                }
            }
            while(size -- != 0){
                TreeNode cur = queue[l++];
                if(cur.left != null){
                    queue[r++] = cur.left;
                }
                if(cur.right != null){
                    queue[r++] = cur.right;
                }
            }
            //变换一下
            rev = !rev;
            ret.add(list);
        }
        return ret;
    }

}
